模拟赛题解/2025.9.26 模拟赛

T1-留影机（camera）

题面

琴团长带可莉去湖边玩啦！

果酒湖畔的树落下了 $n$ 片叶子，第 $i$ 片落下的叶子的美观值为 $m_i=1\times 2\times 3\times\cdots\times i$。这 $n$ 片掉落的叶子总美观值 $k$ 是每片叶子美观值的积。

可莉有一个留影机和很多镜头。如果她使用第 $b$ 个镜头，那么一张照片可以记录 $a^b$ 的美观值。

由于背包容量有限，可莉只能带一个镜头，但她想要把所有的美景都记录下来，而且不想拍太多的照片。作为荣誉骑士，请帮可莉挑一个镜头 $b$，使得她可以用尽量少的照片使得这些照片记录的美观值之和恰好为总美观值 $k$。

$1\leq n\leq10^{18},2\leq a\leq10^{12},1\leq T\leq200$。

题解

考虑枚举 $a$ 的每一个质因数的出现次数，显然 $b$ 的最大值就是所有质因数出现次数的最小值。

注意到一个数 $i$ 的直接出现次数为 $n-i+1$，所以一个数 $x$ 和它的倍数的直接出现总次数就是

$$f(x)=\sum_{i=1}^{\lfloor\frac nx\rfloor} n-xi+1=\frac{(x+x\lfloor\frac nx\rfloor)\lfloor\frac nx\rfloor}2$$

所以一个数的总出现次数就是

$$g(x)=\prod_{i=1}^{\log_xn}f(x^i)$$

直接枚举所有质因数 $x$ 并 $O(\log x)$ 求 $g(x)$，时间复杂度为 $O(T\sqrt a\log a)$。

T2-关禁闭（confine）

题面

这是一道交互题。

可莉又被关进禁闭室啦！

禁闭室的门上有一个密码锁，密码是一个长度为 $n$（$n$ 为偶数）的 $01$ 串 $t$。

可莉想要猜出密码逃出禁闭室。可莉有一个嘟嘟可，可以告诉可莉一些信息。 假设可莉猜测密码是 $s$，那么嘟嘟可会告诉可莉 $s$ 和 $t$ 的关系：

• 如果 $s$ 的长度不为 $n$ 或 $s$ 中的字符不为 $0$ 或 $1$，那么嘟嘟可会坏掉。
• 如果 $s$ 和 $t$ 对应位上相同的个数等于 $n$，那么嘟嘟可会返回 $n$，可莉可以逃出禁闭室。
• 如果 $s$ 和 $t$ 对应位上相同的个数等于 $\frac n2$，那么嘟嘟可会返回 $\frac n2$。
• 否则嘟嘟可会返回 $0$。

由于嘟嘟可的能量有限，可莉只能询问嘟嘟可一定的次数。 可莉不会猜密码，作为荣誉骑士，你能帮她猜到密码逃出禁闭室吗？

$n\leq10^3$。

题解

考虑直接随机化，可以发现实际上 $499$ 次直接随机找到符合 $\frac n2$ 个位置相同的字符串的期望概率几乎是 $1$。

考虑直接钦定一个点，对于剩余所有点，把这个点和另一个点同时反转，如果符合 $\frac n2$ 不变则说明二者正确性相反。

考虑直接把相反的反转，则此时只可能是全对或者全错，两次之内一定能得出正确答案，询问次数为 $n+1$ 次。

总询问次数刚好是 $n+500$。

T3-蹦蹦炸弹（bomb）

题面

“风花节”到了！阿贝多陪可莉玩起了蹦蹦炸弹。

游戏场地是一个由 $n\times m$ 个单位方格组成的巨大草坪。每个方格用坐标 $(r,c)$ 表示，表示在草坪第 $r$ 行第 $c$ 列位置。

可莉和阿贝多轮流操控一枚特殊的蹦蹦炸弹。每轮行动中，当前玩家可以选择将炸弹向正下方 $(r+1,c)$ 或正右方 $(r,c+1)$ 推动一格。

草坪上有 k 个水坑，坐标为 $(x_i,y_i)$，每个水坑有一条鱼，价值为 $v_i$。如果炸弹被推到水坑 $i$ 上，它会立即爆炸，得分为 $v_i$；

如果炸弹被推到场地外也会爆炸，但得分为 $0$。

阿贝多先手，他希望最终得分尽可能小，可莉则希望得分尽可能大。

游戏会在炸弹 爆炸后立马结束。 对于炸弹的每个起始点 $(r,c)$，定义 $g(r,c)$ 为在双方都最优操作的前提下，最终的得分.

你只需要输出 $\sum^n_{i=1}\sum^m_{j=1}g(i,j)\bmod 998244353$ 的值。

$1\leq n,m\leq10^9,1\leq k\leq\min(n\times m,10^5),1\leq x_i\leq n,1\leq y_i\leq m,|v_i|\leq10^9$。

题解

显然有一个 $O(nm)$ 的暴力 $\text{dp}$，设 $f_{i,j,0/1}$ 表示到点 $(i,j)$，先手/后手操作的结果，那么 $f_{i,j,0}=\min(f_{i+1,j,1},f_{i,j+1,1}),f_{i,j,1}=\max(f_{i+1,j,0},f_{i,j+1,0})$，若 $(i,j)$ 有水坑，$f_{i,j,0}=f_{i,j,1}=a_{i,j}$。

发现状态数很多，但转移是 $O(1)$ 的，考虑优化状态数。

首先一个点由谁操作是确定的，所以状态的最后一维可以去掉。

假设当前是先手操作，转移可以转化为 $f_{i,j}=\min(\max(f_{i+2,j},f_{i+1,j+1}),\max(f_{i,j+2},f_{i+1,j+1}))$，这等价于 $f_{i,j}=\max(f_{i+1,j+1},\min(f_{i+2,j},f_{i,j+2}))$。发现一个水坑 $(i,j)$ 只会直接影响到 $(i,j-2),(i-2,j)$，其余的点由它右下角转移过来，那么将会被影响到的点特殊转移，剩下的点按对角线转移即可。

T4-嘟嘟可（dodoco）

题面

可莉在玩游戏！她有 $n$ 个大小不同的嘟嘟可，并用阿贝多制作的小机关让它们能够自己动起来。

第 $i$ 个嘟嘟可走过一单位距离需要 $t_i$ 秒。可莉在赛道上放置了 $m$ 个石碑，第 $i$ 个石碑放在距离起点 $s_i$ 的位置。

游戏规则是这样的： 一开始，所有嘟嘟可都站在第 $0$ 个石碑，并且留下刻印。它们会不断往前走，直到有嘟嘟可到达了某个石碑。

这时可莉会选择到达了任意一个石碑的编号最小的嘟嘟可， 让它在石碑上留下刻印，其余未到达终点的嘟嘟可则会触发机关，被风元素气流吹回到 上一次它们留下刻印的位置（每个嘟嘟可都会触发一次机关）。

如果某个嘟嘟可在第 m 个石碑留下刻印，就算成功到达终点。剩下的嘟嘟可会从自己的刻印位置出发，直到全部到达终点。

不过，吹回嘟嘟可的机关会消耗大量风元素结晶。于是，可莉想知道：如果前 $k$ 个 嘟嘟可一起玩，到最后机关总共会被触发多少次？

设 $c_k$ 表示有 $k$ 个嘟嘟可参赛时，比赛结束前机关总共触发的次数。请你帮可莉算出 $c_1,c_2,\cdots,c_n$ 的值，好让她准备好足够的风元素结晶。

$1\leq n,m\leq10^9,1\leq k\leq\min(n\times m,10^5),1\leq x_i\leq n,1\leq y_i\leq m,|v_i|\leq10^9$。

题解

这里我们称触发机关为“传送”。

我们可以将比赛过程分为 $n\times m$ 轮，每轮有一架嘟嘟可从上一个石碑走至下一个石碑，其余的传送。

考虑每轮是哪个没有传送。发现是走向下一个石碑时间最少且编号最小的。设 表示 $w_{i,j}$ 从 $i$ 号石碑走向 $j-1$ 号石碑所需的时间，发现实际上这个顺序是对这 $n$ 个数组的归并。具体来说就是每次取这 $n$ 个数组中开头最小的那一个，然后删去它，直到删空。

注意到若一个数 $w_{i,l}$ 被删去，且存在一个 $r$ 满足 $(\max_{j=l}^rw_{i,j})\leq w_{i,l}$ ，那么 $w_{i,l\sim r}$ 会被连续删去。证明很显然。那么可以将这些会被连续删去的合并成一个段。

容易发现每个段的段首元素单调递增，即 $w_{i,l_1}<w_{i,l_2}<\cdots<w_{i,l_{m'}}$，其中 $m'$ 为段数。

记 $d_i$ 表示石碑 $i-1$ 到 $i$ 的距离，发现 $w_{i,j}=t_i\times d_j$，而对于相同的 $i$，$t_i$ 相同，所以实际上我们在对 $d_j$ 分段，所以可得 $d_{l_1}<d_{l_2}<\cdots<d_{l_{m'}}$，又由于 $\sum_{i=1}^{m'} d_{l_i}\leq S$，其中 $S$ 为总距离，所以 $m'\leq O(\sqrt S)$。

考虑怎么算答案。每次一个嘟嘟可走至下一个石碑时，对答案的贡献为剩下的没到达终点的嘟嘟可个数，则答案为 $\displaystyle\sum_{i=1}^n\sum_{j\not=i}\sum_{k=1}^m[w_{j,k}\leq w_{i,m}]$，又由于一大段会连续走过去，所以同一段中的贡献相同，只需要算每段的段首，再乘上段的长度即可。所以答案为 $\displaystyle\sum_{i=1}^n\sum_{j\not=i}\sum_{k=1}^m[w_{j,k}\leq w_{i,m}]len_k$。$j\not=i$ 的不好算，将所有的算出来减去 $j=i$ 的即可。

考虑优化这个计算过程。现在计算一次答案的复杂度为 $O(n^2\sqrt S)$，考虑优化一个 $n$。我们固定 $k$，当 $t$ 有序时，发现 $i,j$ 有单调性，那么固定 $i,k$，可以找到 $j$ 的限制 $t_j\leq R_{i,k}$，$R_{i,k}$ 可以双指针求出，可以做前缀和维护 $j$ 的个数。

假设我们已经算出 $i\leq x-1$ 的答案，考虑计算 $x$ 对答案的增量。分两种情况：

• $i=x,j<x$ 时： 增量为 $\displaystyle\sum_{j<x}\sum_{k=1}^{m'}[t_j\leq R_{x,k}]len_k$，枚举 $k$，$O(n)$ 次在 $t_x$ 的位置单点加 $1$，$O(n\sqrt S)$ 次查询 $\leq R_{x,k}$ 的前缀和，可以分块根号平衡。
• $i\leq x,j=x$ 时： 增量为 $\displaystyle\sum_{i\leq x}\sum_{k=1}^{m'}[t_x\leq R_{i,k}]len_k$，枚举 $k$，$O(n\sqrt S)$ 次在 $R_{i,k}$ 的位置单点加 $len_k$，$O(n)$ 次查询 $\geq t_x$ 的后缀和，也可以分块根号平衡。